Năm 2005, nhà sản xuất âm nhạc người Mỹ Rodney "DarkChild" Jerkins và nhà sản xuất Jon Jon Traxx "đã nảy ra ý tưởng thực hiện một ca khúc mang giai điệu old-school, một bài hát cổ điển với tiếng bass và kèn cor đúng chất", ảnh hưởng một phần do tiêu đề của bài hát.[6] Jon Jon Traxx cùng Jerkins, đầu tiên thu âm phần trống bass, kèm theo là các bộ gõ, kèn cor và giọng thu được xếp thành nhiều lớp.[6] Phần sản xuất ca khúc được thực hiện tại phòng thu ở New Jersey của Jerkins và Phòng thu Sony Music ở Thành phố New York.[6]

Jerkins sau đó đã thu âm một bản thử nghiệm của ca khúc với giọng thu của nhạc sĩ người Mỹ Makeba Riddick, người được ghi danh với tư cách là đồng sáng tác ca khúc.[7] Họ sau đó gửi bản thu đến Knowles và đã được chấp thuận. "Déjà Vu" còn có phần lời được đóng góp bởi nhạc sĩ Delisha Thomas, Keli Nicole Price, cùng chồng hiện tại (bạn trai thời điểm ấy) của Knowles, Jay-Z.[6] Anh đã tham gia vào công đoạn cuối cùng, khi Knowles nhìn thấy anh cố gắng hát theo phiên bản thu âm của ca khúc và cô đã ngỏ ý mời anh cùng kết hợp trong bài hát. Jay-Z đã thu âm phần rap cho ca khúc và sau đó xuất hiện với tư cách là một nghệ sĩ hợp tác.[8]

Về công đoạn sản xuất "Déjà Vu", Knowles chia sẻ với MTV News:

Khi tôi thu âm 'Deja Vu'... Tôi đã biết trước khi bắt tay vào thực hiện album của tôi, tôi muốn thêm vào dụng cụ nhạc được thu trực tiếp cho tất cả các bài hát của tôi. Đó đúng là một sự cân bằng [của thể loại âm nhạc trong ca khúc] [...] Nó vẫn rất trẻ trung, mới mẻ và tươi tắn, nhưng nó vẫn có giai điệu soul cổ. Năng lượng [của bài hát] thật tuyệt vời. Đó là bài hát dành cho mùa hè, tôi thề. Tôi cảm nhận được điều đó. Rodney Jerkins thật tuyệt vời, Jay tất nhiên phải xuất hiện, anh đã cầu nguyện cho ca khúc, tôi thì cảm thấy hạnh phúc về ca khúc.[9]